"""
3195. 包含所有 1 的最小矩形面积 I
中等
相关标签
premium lock icon
相关企业
提示
给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。



示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：



这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]

输出： 1

解释：



这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。



提示：

1 <= grid.length, grid[i].length <= 1000
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有一个 1 。
"""
from typing import List


class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        yMin = -1
        for i in range(m):
            if 1 in grid[i]:
                yMin = i
                break
        yMax = -1
        for i in range(m-1,-1,-1):
            if 1 in grid[i]:
                yMax = i
                break
        xmin = 0
        for i in range(n):
            status = True
            for j in range(m):
                if 1 == grid[j][i]:
                    xmin = i
                    status = False
                    break
            if not status:
                break
        xmax = 0
        for i in range(n-1,-1,-1):
            status = True
            for j in range(m):
                if 1 == grid[j][i]:
                    xmax = i
                    status = False
                    break
            if not status:
                break
        return (yMax - yMin + 1 ) * (xmax-xmin + 1 )


    def minimumArea_res(self, grid: List[List[int]]) -> int:
        left = top = float("inf")
        right = bottom = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    left = min(left, j)
                    right = max(right, j)
                    top = min(top, i)
                    bottom = i
        return (right - left + 1) * (bottom - top + 1)

if __name__ == '__main__':
    print(Solution().minimumArea([[0,1,0],[1,0,1]]))